|
Vizualizare problema: string
Titlul problemei
| string
|
Grupa
| Grupa B
|
Problema numarul
| 2
|
Runda numarul
| 12
|
Timp de executie (ms)
| 2000
|
Punctaj maxim pentru problema
| 50
|
Dimensiunea maxima a segmentului
de date (MB)
| 15
|
Dimensiunea maxima a stivei (MB)
| 1
|
Profesorul care a propus problema
| Mugurel Andreica
|
Enuntul problemei
| Se considera alfabetul format
numai din literele mici ‘a’ si ‘b’ si un sir S
format numai din caractere din acest alfabet.
Pe acest alfabet, se defineste relatia de
incluziune, astfel: un sir S1 este inclus în
sirul S2, daca lungimea sirului S2 (egala cu
numarul de caractere ale sirului) este mai
mare sau egala decât a sirului S1 si exista o
pozitie k în sirul S2, astfel încât
S2[k]=S1[1],S2[k+1]=S1[2], .. ,
S2[k+L-1]=S1[L], unde L este lungimea sirului S1,
k+L-1 este mai mic sau egal decât lungimea
sirului S2, iar X[i] reprezinta al i-lea caracter
din sirul X. De exemplu, sirul ‘abba’ este
inclus în sirul ‘babbaba’, dar nu este inclus în
sirul ‘ababab’.
Cerinta
Determinati cel mai scurt sir format numai din
caractere din alfabetul considerat, care sa nu
fie inclus în sirul S.
Date de intrare
Pe prima linie a fisierului de intrare
string.in se afla numarul întreg N, reprezentând
numarul de caractere ale sirului S. Pe
urmatoarea linie se afla cele N caractere, în
ordinea pozitiei lor în sir.
Date de
iesire Pe prima linie a fisierului de iesire
string.out veti afisa numarul întreg L,
reprezentând lungimea minima a unui sir care
nu este inclus în sirul S. Pe a doua linie veti
afisa un astfel de sir. Daca exista mai multe
solutii, puteti afisa oricare dintre ele.
Restrictii si precizari: 1 <= N
<= 500 000 L > 0
Exemplu
string.in 11 aabaaabbbab
string.out 4 aaaa
|
Click aici pentru a va
intoarce |
© 2002 Vâlsan Mihai Liviu Puteti trimite intrebari,
comentarii, sau sugestii la adresa liviuvalsan@yahoo.com |